package com.fang.algorithm.leecode;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 *        I
 *    I000II0I
 * _I0II0IIIIII
 * 0代表雨水 I 代表高度，_代表空
 * 所以能够接收6个单位的雨水
 * @date 2022/5/10 4:03 下午
 **/
public class L42_Trap {
    public static void main(String[] args) {
        int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int ans = trap2(height);
        System.out.println(ans);
    }

    /**
     * 普通方法
     * 时间O(n^2)
     * 空间O(1)
     */
    private static int trap1(int[] height) {
        int ans = 0;
        if (height.length < 2) {
            return ans;
        }
        for (int i = 0; i < height.length; i++) {
            int leftMax = 0, rightMax = 0;
            // 向左查找最大值
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, height[j]);
            }
            // 向右查找最大值
            for (int j = i; j < height.length; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
            // 计算当前位置的承接量
            int currAns = Math.min(leftMax, rightMax) - height[i];
            // 汇总
            ans += currAns;
        }
        return ans;
    }

    /**
     * 动态规划
     * 时间O(n)
     * 空间O(n)
     */
    private static int trap2(int[] height) {
        int ans = 0;
        if (height.length < 2) {
            return ans;
        }
        // 创建每个节点及记录左右的最大值
        int[] dpRight = new int[height.length];
        int[] dpLeft = new int[height.length];
        // 从左往右 找 元素左边的最大值
        dpLeft[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            dpLeft[i] = Math.max(dpLeft[i - 1], height[i]);
        }
        // 从右往左 找 元素右边的最大值
        dpRight[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            dpRight[i] = Math.max(dpRight[i + 1], height[i]);
        }
        //
        for (int i = 0; i < height.length; i++) {
            ans += Math.min(dpLeft[i], dpRight[i]) - height[i];
        }
        return ans;
    }
}
